package algorithmExample.BinarySearch;

/**
 * @author: zhang.rongqing
 * @since: 2019/11/2
 */
//给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
//
//        返回被除数 dividend 除以除数 divisor 得到的商。
//
//        示例 1:
//
//        输入: dividend = 10, divisor = 3
//        输出: 3
//        示例 2:
//
//        输入: dividend = 7, divisor = -3
//        输出: -2
//        说明:
//
//        被除数和除数均为 32 位有符号整数。
//        除数不为 0。
//        假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231,  231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
public class DivideTwoInteger {
    //正常计算，会有超时
    public int divide(int dividend, int divisor) {
        int sign = 1;
        int result = 0;
        long ldividend = Math.abs(dividend), ldivisor = Math.abs(divisor);
        if ((dividend ^ divisor) < 0) {
            sign = -1;
        }
        if (ldivisor < ldividend) {
            return 0;
        }
        while (ldivisor >= ldividend) {
            result++;
            ldivisor -= ldividend;
        }
        return sign == 1 ? result : result * sign;
    }

    public int divide2(int dividend, int divisor) {
        long result = divide((long) dividend, (long) divisor);
        if (result >= Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        } else {
            return (int) result;
        }
    }

    //除数叠加倍数
    public long divide(long dividend, long divisor) {
        int sign = 1;
        long ans = 1;
        long ldivisor = opposit(divisor), ldividend = opposit(dividend);
        long origin_dividend = ldividend;
        long origin_divisor = ldivisor;
        if ((dividend ^ divisor) < 0) {
            sign = -1;
        }
        if (ldividend < ldivisor) {
            return 0;
        }
        //减少第一次
        ldividend -= ldivisor;
        while (ldividend >= ldivisor) {
            ans = ans + ans;
            ldivisor = ldivisor + ldivisor;
            ldividend -= ldivisor;
        }
        ans = ans + divide(origin_dividend - ldivisor, origin_divisor);
        return sign == 1 ? ans : ans * sign;
    }

    public long opposit(long x) {
        if (x > 0) {
            return x;
        }
        //去补数+1
        return ~x + 1;
    }

    public static void main(String[] args) {
//        测试异或结果
        int a = 10;
        int b = 3;
        int c = 123213213;
        int d = -111111;
//        System.out.println(a^b);
//        System.out.println(a^c);
//        System.out.println(a^d);

//        int result = new DivideTwoInteger().divide(a,b);
//        System.out.println(result);
        int result2 = new DivideTwoInteger().divide2(a, b);
        System.out.println(result2);
    }
}
